The present invention relates to data representations of geographic features and more particularly, the present invention relates to a way to measure how closely one geometric shape matches another geometric shape.
The need to compare geometric shapes arises in various applications relating to the use of data representations of geographic features. Some of these applications include vehicle positioning, measuring geographic database accuracy, and road sign recognition. For instance, in a vehicle positioning application, one way to determine the position of a moving vehicle with respect to a map database that represents the road network upon which the vehicle is traveling is to find the best match between the vehicle""s path, as determined by processing sensor data, and the data representation of the roads that form the road network upon which the vehicle is traveling.
One standard method for determining geometric distortion (i.e., how much one geometric shape is different from another geometric shape) involves finding the area between the two shapes. FIG. 1 illustrates this standard method. FIG. 1 shows a geometric shape labeled xe2x80x9cshape Axe2x80x9d and another shape labeled xe2x80x9cshape B.xe2x80x9d In order for this standard process to yield a true measure of distortion, it is required that the shapes be aligned to minimize the area. This alignment is shown in FIG. 1 by the line labeled xe2x80x9cShape B aligned with Shape A.xe2x80x9d However, it is not always clear how to perform this alignment, especially automatically. An alternative is to compute the area for all translations and rotations of the two geometric shapes. The minimum area computed is a measure of the geometric distortion between the two shapes. This process can be time consuming and computationally intensive.
Accordingly, there exists a need for an improved way to compare one geometric shape to another geometric shape.
To address these and other objectives, the present invention provides a method for comparing geometric shapes to each other. The method includes determination of a rotational variation coefficient. Tangent vectors at corresponding locations along the geometric shapes to be compared are determined and the angle between pairs of tangent vectors for each of these locations is plotted as a function of the distance along the shapes. The variance of the plot around the mean value is the rotational variation coefficient. This process defines a rotational variation metric which indicates how closely the two geometric shapes match.
The rotational variation metric can be used in various applications that use geographic data. The rotational variation metric can be used in vehicle positioning. By using the rotational variation metric to compare the vehicle trajectory determined from sensors to the paths of roads as represented in a map database, the location on the road on which the vehicle is likely to be located can be determined.
The rotational variation metric can be also be used for road sign recognition. The outline of an object in a detected image is compared to a plurality of different road sign shape templates. Using the rotational variation metric, the sign shape template that most closely matches the outline of the object in the detected image indicates the most likely sign.
The rotational variation metric can also be used for evaluating geographic database accuracy. The shapes of data representations of geographic features represented in a geographic database are compared to the ground truth representations of the actual features. The rotational variation metric indicates how closely the geographic database representation of each geographic feature matches the actual geographic feature.